#pragma once

#include <vector>
#include <algorithm>
#include <functional>

#include "compare.h"
#include "util.h"

#include <time.h>

using namespace std;

template<typename T>
class Quick
{
  vector<T> _v;

  function<bool(const T&,const T&)> _compare;

  // um índice tal qual todos à sua esquerda são menores que ele
  int _pivot(int begin,int end)
  {
    // pivot aleatório. Não teve um bom desempenho :-(
    //return (rand() % (end - begin)) + begin;

    // usa como pivot o elemento "do meio"
    return (begin + end) / 2;
  }

  int _partition(int begin, int end, int pivot)
  {
    swap(_v[pivot],_v[end]);

    int i = begin, s = i;

    for (; i < end; i++) {
      if (_compare(_v[end],_v[i])) {
        swap(_v[s],_v[i]);
        s++;
      }
    }

    swap(_v[s],_v[end]);

    return s;
  }

  void _sort(int begin, int end)
  {
    if (end <= begin) {
      return;
    }

    int p = _pivot(begin,end);

    p = _partition(begin,end,p); // particionar no pivot

    _sort(begin,p - 1); // chama recursivo antes do pivot

    _sort(p + 1,end); // chama recursivo depois do pivot
  }

public:
  Quick(const vector<T> &v, const function<bool(const T&, const T&)> &c = CompareMax<T>()):
  _v(v),
  _compare(c)
  {
  }

  vector<T> sort()
  {
    _sort(0,_v.size() - 1);
    return _v;
  }
};
